import java.util.Arrays;
import java.util.Map;

/**
 * @author luoqingbo
 * @create 2024/5/6 9:38
 */
public class Leetcode741 {
//    输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
//    输出：5
//    解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
//    在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
//    然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
//    总共捡到 5 个樱桃，这是最大可能值。

    //    0 表示这个格子是空的，所以你可以穿过它。
//    1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
//    -1 表示这个格子里有荆棘，挡着你的路。
    //
    // 0 1 -1
    // 1 0 -1
    // 1 1  1
    public static void main(String[] args) {
//        int[][] grid = {{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}};
        int[][] grid = {{1, 1, -1, 1, 1, 1, 0, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 0, 1},
                {1, 1, 1, 0, 1, 1, 0, 1, 0, 1, -1, 1, 1, 1, 1, 1, 1, 0, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 0, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1},
                {1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, -1, 1, 1, 1},
                {1, -1, -1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 0, 1, 1, 1, 1, 1, -1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
                {0, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
                {1, 1, -1, 1, 1, 1, -1, 1, 0, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1},
                {0, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1},
                {1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, -1, 0, 1, 0, -1, 1},
                {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, -1, 0},
                {1, 1, 1, 1, 1, 1, -1, 1, 0, 1, 1, 1, 1, -1, 1, 1, 1, 0, 1, 1},
                {1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1},
                {-1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 0, 0, 1, 0, 1, 1},
                {0, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1},
                {1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1},
                {1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, 1, 1, 1, 1, 1, -1},
                {1, 1, 1, -1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, -1, 0, 1, 1},
                {1, 1, -1, 0, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 0, 1},
                {-1, 0, 0, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 0, 1, 0, 0, 1, -1, 1}};
        //int[][] grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
        //cherryPickup(grid);
        System.out.println(cherryPickup(grid));
        int a;
        System.out.println(a=1);
    }

    public static int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][][] memo = new int[n][n][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    Arrays.fill(memo[i][j][k], -2);
                }
            }
        }
        int ans = dfs(0, 0, 0, 0, grid, memo);
        return ans < 0 ? 0 : ans;
    }

    private static int dfs(int x1, int y1, int x2, int y2, int[][] grid, int[][][][] memo) {
        //边界判断
        int n = grid.length;
        if (x1 >= n || y1 >= n || grid[x1][y1] == -1 || x2 >= n || y2 >= n || grid[x2][y2] == -1) {
            return -1;
        }

        if (memo[x1][y1][x2][y2] != -2) {
            return memo[x1][y1][x2][y2];
        }

        if (x1 == n - 1 && x2 == n - 1 && y1 == n - 1 && y2 == n - 1) {
            if (grid[x1][y1] == 1) {
                return 1;
            } else {
                return 0;
            }
        }

        //x1向下,x2向下
        int sum1 = dfs(x1 + 1, y1, x2 + 1, y2, grid, memo);

        //x1向下,x2向右
        int sum2 = dfs(x1 + 1, y1, x2, y2 + 1, grid, memo);

        //x1向右,x2向下
        int sum3 = dfs(x1, y1 + 1, x2 + 1, y2, grid, memo);

        //x1向右，x2向右
        int sum4 = dfs(x1, y1 + 1, x2, y2 + 1, grid, memo);
        if (sum1 == -1 && sum2 == -1 && sum3 == -1 && sum4 == -1) {
            return memo[x1][y1][x2][y2]=-1;
        }
        int max = Math.max(Math.max(sum1, sum2), Math.max(sum3, sum4));
        max += ((x1 == x2 && y1 == y2) ? grid[x1][y1] : grid[x1][y1] + grid[x2][y2]);
        memo[x1][y1][x2][y2] = max;
        return memo[x1][y1][x2][y2];
    }

//    private static void dfs(int x, int y, int[][] grid, int cherryNum) {
//        //边界判断
//        if (x >= grid.length || y >= grid[0].length || grid[x][y] == -1) {
//            return;
//        }
//        if (grid[x][y] == 1) {
//            cherryNum++;
//        }
//        //判断是否位终点
//        if (x == grid.length - 1 && y == grid[0].length - 1) {
//            ans = Math.max(ans, cherryNum);
//        }
//
//        //向下
//        dfs(x + 1, y, grid, cherryNum);
//        //向右
//        dfs(x, y + 1, grid, cherryNum);
//    }
}
